We determine the complexity of several constraint satisfaction problems usingthe heuristic algorithm, WalkSAT. At large sizes N, the complexity increasesexponentially with N in all cases. Perhaps surprisingly, out of all the modelsstudied, the hardest for WalkSAT is the one for which there is a polynomialtime algorithm.
展开▼